#include "graph.h"


/*
createGraph:根据用户输入的顶点和关系建立一个图(邻接矩阵)
            顶点和关系通过键盘输入
返回值:
    返回建立好的图的地址
*/
Graph *createGraph()
{
    //为图分配存储空间（malloc），并且初始化
    Graph * g = (Graph *)malloc(sizeof(*g));
    g->vexnum = 0;
    g->arcnum = 0;
    //g->V[]存储的是顶点集合,将其初始化
    int i,j;
    for(i = 0;i<MAXN;i++)
    {
        g->V[i] = 0;
    }
    //g->A[][],存储的是图中的所有关系，将其初始化
    for(i = 0;i<MAXN;i++)
    {
        for(j = 0;j<MAXN;j++)
        {
            g->A[i][j] = VERY_BIG;//表示没有关系
        }
    }

    //输入所有的顶点,把顶点保存到顶点数组
    printf("请输入顶点：\n");
    scanf("%s",g->V);
    g->vexnum = strlen(g->V);//顶点元数个数就是字符串的字节长度
    getchar();//scanf(%s) 不接收回车,缓存区存在一个回车,getchar用来接收回车
    
    //输入所有顶点元数个数之间的关系，将关系保存在矩阵中
    printf("Please input all the Releation:\n");
    while(1)
    {
        //输入顶点字符，终点字符，权值
        //定义顶点元素和边
        VType s,p;//起点和终点
        AdjType w;//权值
        scanf("%c%c%d",&s,&p,&w);
        getchar();//scanf(%s) 不接收回车,缓存区存在一个回车,getchar用来接收回车
        if(s == '#')
        {
            break;
        }
        //把s-->p权为w的关系保存到邻接矩阵g->A[i][j]中
        //其中i是起点s在顶点数组V中的下标
        //其中j是终点p在顶点数组V中的下标
        i = chIndex(s,g->V,g->vexnum);
        j = chIndex(p,g->V,g->vexnum);
        if(i == -1 || j == -1)//在chIndex中没有找到
        {
            continue;//跳过下面的步骤，再循环
        }
        g->A[i][j] = w;
        g->arcnum++;
    }
    //返回创建的图的地址 
    return g;
}

/*
chIndex:返回指定元素ch在数组中第一次出现的下标,如果数组中不存在ch则返回-1
@ch:你要查找下标的字符
@str:数组的首地址
@num:数组中的元素个数
返回值:
    指定元素ch在数组中第一次出现的下标,如果数组中不存在ch则返回-1
*/
int chIndex(VType ch,VType *str,int num)
{
    //遍历一遍
    for(int i = 0;i<num;i++)
    {
        if(str[i] == ch)
        {
            return i;          //在数组中找到了对应的字符
        }
    }
    return -1;          //没找到返回-1
}

/*
printGraph:打印一个指定的图(顶点数组,邻接矩阵)
        验证图是否保存成功
@g:指针,指向你要打印的图
返回值:无
*/

void printGraph(Graph *g)
{
    if(g == NULL)
    {
        return;
    }
    int i,j;
    //打印顶点个数
    printf("Vextex num:%d\n",g->vexnum);
    //打印顶点数组:
    printf("Vextex Data:\n");
    for(i=0;i<g->vexnum;i++)
    {
        printf("%c  ",g->V[i]);
    }
    //打印边的条数:
    printf("\nEDGE num:%d\n",g->arcnum);
    //打印邻接矩阵
    printf("邻接矩阵:\n");
    for(i=0;i<g->vexnum;i++)
    {
        for(j=0;j<g->vexnum;j++)
        {
            if(g->A[i][j] == VERY_BIG)
            {
                printf("#\t");
            }else 
            {
                printf("%d\t",g->A[i][j]);
            }
        }
        printf("\n");
    }
}

int Visited[MAXN] = {0}; //未访问过的顶点标记为0,已经访问过的顶点标记为1



//获取顶点v的第一个邻接点的下标
int getFirstAdj(Graph *g,int v)
{
    int i;
    for(i=0;i<g->vexnum;i++)
    {
        if(g->A[v][i] != VERY_BIG)
        {
            return i;
        }
    }
    return -1; //说明v没有邻接点
}

//获取顶点v基于vi的下一个邻接点
int getNextAdj(Graph *g,int v,int vi)
{
    int i;
    for(i=vi+1;i<g->vexnum;i++)
    {
        if(g->A[v][i] != VERY_BIG)
        {
            return i;
        }
    }
    return -1; //表示v从vi开始没有下一个邻接点了(vi是v的最后一个邻接点)
}

void DFStravel(Graph *g)   //按照深度优先搜索的方法访问图g中所有的顶点
{
    for(int i=0;i > g->vexnum;i++)
    {
        Visited[i] = 0;
    }
    for(int i=0;i < g->vexnum;i++)
    {
        if(Visited[i] == 0)//i为下标的顶点从未被访问
        {
            DFS(g,i);
        }
    }
}

/*从顶点开始深度优先搜索遍历图g*/
void DFS(Graph *g,int v)
{
    //访问V本身
    printf("%c",g->V[v]);
    //标记已经被访问过的顶点
    Visited[v] = 1;
    //如果没有访问，开始访问
    for(int vi = getFirstAdj(g,v);vi != -1;vi = getNextAdj(g,v,vi))
    {
        if(Visited[vi] == 0)
        {
            DFS(g,vi);
        }
    }

}

